COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.device xgp
C00004 00003	.BEGIN NOFILL
C00026 00004	.VERBATIM
C00042 00005	.SKIP TO LINE 1
C00044 ENDMK
C⊗;
.device xgp
.EVENLEFTBORDER←ODDLEFTBORDER←1000
.require "pubmac[206, LSP]" source_file
.font 1 "basl30" <<text>>
.font 2 "bdr30" <<sym>>
.font 3 "basi30" <<var>>
.font 4 "basb30" <<bold>>
.font 5 "bdr30" <<const>>
.font 6 "fix20"
.PAGE FRAME 52 HIGH 90 WIDE;
.AREA TEXT LINES 4 TO 50 CHARS 1 TO 83;
.TITLE AREA HEADING LINES 1 TO 3 CHARS 1 TO 83;
.TITLE AREA FOOTING LINE 51 CHARS 1 TO 83;
.PLACE TEXT;
.SECNAME←NULL;
.turn on "%#π" ;
.<<TURN ON "@" FOR "∂" ;>>
.every heading(, {SECNAME}, {page}) ;
.<<EVERY FOOTING(, {SECTION!}.{SUBSECTION!}, )>>
.AT 8 ⊂"%1        %*"⊃ ;
.AT 16 ⊂"%1                %*"⊃ ;
.<<AT "\→" KK "." ; ⊂KK ← CHAR⊃ ;>>
.NEXT PAGE
.BEGIN NOFILL
.VARIABLE CHW
.CHW ← CHARW
.TURN ON "∂{%←"
.TURN ON "/" FOR "α"
.AT "∂∂(" CH ")" ⊂ CHARW←CH}∂(2){CHARW←CHW ⊃
←%1CS206		GAME TREE FUNCTIONS		FALL 1974
.TURN OFF "βα#\←∞↑↓∪"



.FILL
These are functions for searching game trees,
applied to the game of tic-tac-toe.
The functions are listed
in both blackboard notation and S-expression notation.  Following the
listings are examples of their use.
.NOFILL

%1Functions on file XBASIC:

∂∂(48)%3orlis%2[%3pred%2, %3u%2]%2 %2← %2¬%4n %3u%2 %2∧ %2[%3pred%2 %4a %3u%2 %2∨ %3orlis%2[%3pred%2, %4d %3u%2]%2]



∂∂(48)%3andlis%2[%3pred%2, %3u%2]%2 %2← %4n %3u%2 %2∨ %2[%3pred%2 %4a %3u%2 %2∧ %3andlis%2[%3pred%2, %4d %3u%2]%2]



∂∂(48)%3mapcar2%2[%3fn%2, %3u%2, %3v%2]%2 %2← %4if%2 %4n %3u%2 %4then%2 %5NIL%2 %4else%2 %3fn%2[%4a %3u%2, %4a %3v%2]%2 %2. %3mapcar2%2[%3fn%2, %4d %3u%2, %4d %3v%2]



∂∂(48)%3mapchoose%2[%3pred%2, %3fn%2, %3u%2]%2 %2← 
∂∂(80)%4if%2 %4n %3u%2 %4then%2 %5NIL
∂∂(80)%4else if%2 %3pred%2 %4a %3u%2 %4then%2 %3fn%2 %4a %3u%2 %2. %3mapchoose%2[%3pred%2, %3fn%2, %4d %3u%2]
∂∂(80)%4else%2 %3mapchoose%2[%3pred%2, %3fn%2, %4d %3u%2]



∂∂(48)%3mapapp%2[%3fn%2, %3u%2]%2 %2← %4if%2 %4n %3u%2 %4then%2 %5NIL%2 %4else%2 %3fn%2 %4a %3u%2 %2* %3mapapp%2[%3fn%2, %4d %3u%2]



∂∂(48)%3prup%2[%3u%2, %3v%2]%2 %2← 
∂∂(80)%4if%2 %4n %3u%2 %4then%2 %2[%4if%2 %4n %3v%2 %4then%2 %5NIL%2 %4else%2 %3error%2 %2(%5V%2 %5LONGER%2 %2 %2`%5-%2' %2 %5PRUP%2)%2]
∂∂(80)%4else if%2 %4n %3v%2 %4then%2 %3error%2 %2(%5U%2 %5LONGER%2 %2 %2`%5-%2' %2 %5PRUP%2)
∂∂(80)%4else%2 %2[%4a %3u%2 %2. %4a %3v%2]%2 %2. %3prup%2[%4d %3u%2, %4d %3v%2]



∂∂(48)%3listsubt%2[%3u%2, %3v%2]%2 %2← %3listsubta%2[%3u%2, %3length%2 %3u%2 %2- %3length%2 %3v%2, %5NIL%2]



∂∂(48)%3listsubta%2[%3u%2, %3n%2, %3z%2]%2 %2← %4if%2 %3equal%2[%3n%2, %50%2]%2 %4then%2 %3z%2 %4else%2 %3listsubta%2[%4d %3u%2, %3sub1%2 %3n%2, %4a %3u%2 %2. %3z%2]



∂∂(48)%3contained%2[%3u%2, %3v%2]%2 %2← %4n %3u%2 %2∨ %2[%4a %3u%2 %2ε %3v%2 %2∧ %3contained%2[%4d %3u%2, %3v%2]%2]



∂∂(48)%3delete%2[%3x%2, %3u%2]%2 %2← %4if%2 %4n %3u%2 %4then%2 %5NIL%2 %4else if%2 %3equal%2[%3x%2, %4a %3u%2]%2 %4then%2 %4d %3u%2 %4else%2 %4a %3u%2 %2. %3delete%2[%3x%2, %4d %3u%2]



∂∂(48)%3pickout%2[%3pred%2, %3u%2]%2 %2← %3pickouta%2[%3pred%2, %3u%2, %5NIL%2, %5NIL%2]



∂∂(48)%3pickouta%2[%3pred%2, %3u%2, %3x%2, %3y%2]%2 %2← 
∂∂(80)%4if%2 %4n %3u%2 %4then%2 %3x%2 %2. %3y
∂∂(80)%4else if%2 %3pred%2 %4a %3u%2 %4then%2 %3pickouta%2[%3pred%2, %4d %3u%2, %4a %3u%2 %2. %3x%2, %3y%2]
∂∂(80)%4else%2 %3pickouta%2[%3pred%2, %4d %3u%2, %3x%2, %4a %3u%2 %2. %3y%2]


%1Functions on file XGAME:

∂∂(48)%3valmax%2[%3u%2, %3alpha%2, %3beta%2]%2 %2← 
∂∂(80)%4if%2 %4n %3u%2 %4then%2 %3alpha
∂∂(80)%4else%2 %2/{%4if%2 %3ter%2[%3rectify%2 %4a %3u%2, %3alpha%2, %3beta%2]%2 %4then%2 %3imval%2 %4a %3u%2 %4else%2 %3valmin%2[%3successors%2 %4a %3u%2, %3alpha%2, %3beta%2]%2}
∂∂(112)%2[λ%3s%2. %4if%2 %2¬%2[%3s%2 %2> %3alpha%2]%2 %4then%2 %3valmax%2[%4d %3u%2, %3alpha%2, %3beta%2]
∂∂(168)%4else if%2 %3s%2 %2< %3beta%2 %4then%2 %3valmax%2[%4d %3u%2, %3s%2, %3beta%2]
∂∂(168)%4else%2 %3beta%2]



∂∂(48)%3valmin%2[%3u%2, %3alpha%2, %3beta%2]%2 %2← 
∂∂(80)%4if%2 %4n %3u%2 %4then%2 %3beta
∂∂(80)%4else%2 %2/{%4if%2 %3ter%2[%3rectify%2 %4a %3u%2, %3alpha%2, %3beta%2]%2 %4then%2 %3imval%2 %4a %3u%2 %4else%2 %3valmax%2[%3successors%2 %4a %3u%2, %3alpha%2, %3beta%2]%2}
∂∂(112)%2[λ%3s%2. %4if%2 %2¬%2[%3s%2 %2> %3alpha%2]%2 %4then%2 %3alpha
∂∂(168)%4else if%2 %3s%2 %2< %3beta%2 %4then%2 %3valmin%2[%4d %3u%2, %3alpha%2, %3s%2]
∂∂(168)%4else%2 %3valmin%2[%4d %3u%2, %3alpha%2, %3beta%2]%2]



∂∂(48)%3linemax%2[%3u%2, %3line%2, %3alpha%2, %3beta%2]%2 %2← 
∂∂(80)%4if%2 %4n %3u%2 %4then%2 %3alpha%2 %2. %3line
∂∂(80)%4else%2 %2/{%4if%2 %3ter%2[%3rectify%2 %4a %3u%2, %3alpha%2, %3beta%2]%2 %4then%2 %2<%3imval%2 %4a %3u%2>
∂∂(167)%4else%2 %3linemin%2[%3successors%2 %4a %3u%2, %3beta%2 %2. %2 %2`%5BETA-CUTOFF%2' %2, %3alpha%2, %3beta%2]%2}
∂∂(112)%2[λ%3s%2. %4if%2 %2¬%2[%4a %3s%2 %2> %3alpha%2]%2 %4then%2 %3linemax%2[%4d %3u%2, %3line%2, %3alpha%2, %3beta%2]
∂∂(168)%4else if%2 %4a %3s%2 %2< %3beta%2 %4then%2 %3linemax%2[%4d %3u%2, %3ext%2 %4a %3u%2 %2. %4d %3s%2, %4a %3s%2, %3beta%2]
∂∂(168)%4else%2 %3beta%2 %2. %3line%2]



∂∂(48)%3linemin%2[%3u%2, %3line%2, %3alpha%2, %3beta%2]%2 %2← 
∂∂(80)%4if%2 %4n %3u%2 %4then%2 %3beta%2 %2. %3line
∂∂(80)%4else%2 %2/{%4if%2 %3ter%2[%3rectify%2 %4a %3u%2, %3alpha%2, %3beta%2]%2 %4then%2 %2<%3imval%2 %4a %3u%2>
∂∂(167)%4else%2 %3linemax%2[%3successors%2 %4a %3u%2, %3alpha%2 %2. %2 %2`%5ALPHA-CUTOFF%2' %2, %3alpha%2, %3beta%2]%2}
∂∂(112)%2[λ%3s%2. %4if%2 %2¬%2[%4a %3s%2 %2> %3alpha%2]%2 %4then%2 %3alpha%2 %2. %3line
∂∂(168)%4else if%2 %4a %3s%2 %2< %3beta%2 %4then%2 %3linemin%2[%4d %3u%2, %3ext%2 %4a %3u%2 %2. %4d %3s%2, %3alpha%2, %4a %3s%2]
∂∂(168)%4else%2 %3linemin%2[%4d %3u%2, %3line%2, %3alpha%2, %3beta%2]%2]



∂∂(48)%3treemax%2[%3u%2, %3trmax%2, %3trmin%2, %3alpha%2, %3beta%2]%2 %2← 
∂∂(80)%4if%2 %4n %3u%2 %4then%2 %2<%3alpha%2, %3trmax%2, %3trmin%2>
∂∂(80)%4else%2 %2/{%4if%2 %3ter%2[%3rectify%2 %4a %3u%2, %3alpha%2, %3beta%2]%2 %4then%2 %2/{%3imval%2 %4a %3u%2}%2[λ%3v%2. %2<%3v%2, %2<%3v%2>%2, %2<%3v%2>%2>%2]
∂∂(167)%4else%2 %3treemin%2[%3successors%2 %4a %3u%2, %5NIL%2, %3beta%2 %2. %2 %2`%5BETA-CUTOFF%2' %2, %3alpha%2, %3beta%2]%2}
∂∂(112)%2[λ%3s%2. %4if%2 %2¬%2[%4a %3s%2 %2> %3alpha%2]%2 %4then%2 %3treemax%2[%4d %3u%2, %3trmax%2, %2[%3ext%2 %4a %3u%2 %2. %4add %3s%2]%2 %2. %3trmin%2, %3alpha%2, %3beta%2]
∂∂(168)%4else if%2 %4a %3s%2 %2< %3beta%2 %4then%2 %3treemax%2[%4d %3u%2, %3ext%2 %4a %3u%2 %2. %4ad %3s%2, %2[%3ext%2 %4a %3u%2 %2. %4add %3s%2]%2 %2. %3trmin%2, %4a %3s%2, %3beta%2]
∂∂(168)%4else%2 %2<%3beta%2, %3ext%2 %4a %3u%2 %2. %4ad %3s%2, %5NIL%2>%2]



∂∂(48)%3treemin%2[%3u%2, %3trmax%2, %3trmin%2, %3alpha%2, %3beta%2]%2 %2← 
∂∂(80)%4if%2 %4n %3u%2 %4then%2 %2<%3beta%2, %3trmax%2, %3trmin%2>
∂∂(80)%4else%2 %2/{%4if%2 %3ter%2[%3rectify%2 %4a %3u%2, %3alpha%2, %3beta%2]%2 %4then%2 %2/{%3imval%2 %4a %3u%2}%2[λ%3v%2. %2<%3v%2, %2<%3v%2>%2, %2<%3v%2>%2>%2]
∂∂(167)%4else%2 %3treemax%2[%3successors%2 %4a %3u%2, %3alpha%2 %2. %2 %2`%5ALPHA-CUTOFF%2' %2, %5NIL%2, %3alpha%2, %3beta%2]%2}
∂∂(112)%2[λ%3s%2. %4if%2 %2¬%2[%4a %3s%2 %2> %3alpha%2]%2 %4then%2 %2<%3alpha%2, %5NIL%2, %3ext%2 %4a %3u%2 %2. %4add %3s%2>
∂∂(168)%4else if%2 %4a %3s%2 %2< %3beta%2 %4then%2 %3treemin%2[%4d %3u%2, %2[%3ext%2 %4a %3u%2 %2. %4ad %3s%2]%2 %2. %3trmax%2, %3ext%2 %4a %3u%2 %2. %4add %3s%2, %3alpha%2, %4a %3s%2]
∂∂(168)%4else%2 %3treemin%2[%4d %3u%2, %2[%3ext%2 %4a %3u%2 %2. %4ad %3s%2]%2 %2. %3trmax%2, %3trmin%2, %3alpha%2, %3beta%2]%2]



∂∂(48)%3rectify%2 %3p%2 %2← 
∂∂(80)%4prog%2 %2[%3z%2, %3q%2]
∂∂(153)%3q%2 %2← %3commontail%2[%3p%2, %3p1%2]
∂∂(121)%3l1%2 %4if%2 %3equal%2[%3q%2, %3p1%2]%2 %4then%2 %3go%2 %3l2
∂∂(153)%3revert%2[]
∂∂(153)%3go%2 %3l1
∂∂(116)%3l2%2 %3z%2 %2← %3listsubt%2[%3p%2, %3p1%2]
∂∂(115)%3l3%2 %4if%2 %4n %3z%2 %4then%2 %3return%2 %3p
∂∂(153)%3update%2 %4a %3z
∂∂(153)%3z%2 %2← %4d %3z
∂∂(153)%3go%2 %3l3



∂∂(48)%3commontail%2[%3u%2, %3v%2]%2 %2← %3reverse%2 %3commonhead%2[%3reverse%2 %3u%2, %3reverse%2 %3v%2]



∂∂(48)%3commonhead%2[%3u%2, %3v%2]%2 %2← %4if%2 %4n %3u%2 %2∨ %4n %3v%2 %2∨ %2¬%3equal%2[%4a %3u%2, %4a %3v%2]%2 %4then%2 %5NIL%2 %4else%2 %4a %3u%2 %2. %3commonhead%2[%4d %3u%2, %4d %3v%2]


Functions on file TICTAC:

∂∂(48)%3commence%2[]%2 %2← 
∂∂(80)%4prog%2 %2[%2]
∂∂(153)%3array%2[%3lines%2, %5T%2, %512%2]
∂∂(153)%3array%2[%3xcount%2, %544%2, %511%2]
∂∂(153)%3array%2[%3ocount%2, %544%2, %511%2]
∂∂(153)%3store%2[%3lines%2 %51%2, %2(%51%2 %54%2 %57%2)%2]
∂∂(153)%3store%2[%3lines%2 %52%2, %2(%51%2 %55%2)%2]
∂∂(153)%3store%2[%3lines%2 %53%2, %2(%51%2 %56%2 %510%2)%2]
∂∂(153)%3store%2[%3lines%2 %54%2, %2(%52%2 %54%2)%2]
∂∂(153)%3store%2[%3lines%2 %55%2, %2(%52%2 %55%2 %57%2 %510%2)%2]
∂∂(153)%3store%2[%3lines%2 %56%2, %2(%52%2 %56%2)%2]
∂∂(153)%3store%2[%3lines%2 %57%2, %2(%53%2 %54%2 %510%2)%2]
∂∂(153)%3store%2[%3lines%2 %510%2, %2(%53%2 %55%2)%2]
∂∂(153)%3store%2[%3lines%2 %511%2, %2(%53%2 %56%2 %57%2)%2]



∂∂(48)%3ext%2 %3p%2 %2← %4a %3p



∂∂(48)%3newgame%2[]%2 %2← 
∂∂(80)%4prog%2 %2[%3n%2]
∂∂(153)%3n%2 %2← %50
∂∂(133)%3l%2 %3n%2 %2← %3add1%2 %3n
∂∂(153)%3store%2[%3xcount%2 %3n%2, %50%2]
∂∂(153)%3store%2[%3ocount%2 %3n%2, %50%2]
∂∂(153)%4if%2 %3n%2 %2< %510%2 %4then%2 %3go%2 %3l
∂∂(153)%3p1%2 %2← %5NIL
∂∂(153)%3xs%2 %2← %5NIL
∂∂(153)%3os%2 %2← %5NIL
∂∂(153)%3bs%2 %2← %2(%51%2 %52%2 %53%2 %54%2 %55%2 %56%2 %57%2 %510%2 %511%2)
∂∂(153)%3w%2 %2← %5NIL
∂∂(153)%3level%2 %2← %50
∂∂(153)%3count%2 %2← %50
∂∂(153)%3return%2 %2(%5NEW%2 %5GAME%2)



∂∂(48)%3ter%2[%3p%2, %3alpha%2, %3beta%2]%2 %2← 
∂∂(80)%2¬%4n %3p
∂∂(80)%2∧ %2[%3equal%2[%3level%2, %511%2]
∂∂(122)%2∨ %511%2 %2- %3level%2 %2< %3alpha
∂∂(122)%2∨ %5-11%2 %2+ %3level%2 %2> %3beta
∂∂(122)%2∨ %2[%4prog%2 %2[%3n%2]
∂∂(237)%3n%2 %2← %50
∂∂(200)%3l2%2 %3n%2 %2← %3add1%2 %3n
∂∂(237)%4if%2 %3equal%2[%53%2, %4if%2 %3w%2 %4then%2 %3xcount%2 %3n%2 %4else%2 %3ocount%2 %3n%2]%2 %4then%2 %3return%2 %5T
∂∂(237)%4if%2 %3n%2 %2< %510%2 %4then%2 %3go%2 %3l2
∂∂(237)%3return%2 %5NIL%2]%2]



∂∂(48)%3imval%2 %3p%2 %2← 
∂∂(80)%4if%2 %3w%2 %4then%2 
∂∂(112)%2[%4prog%2 %2[%3n%2]
∂∂(194)%3n%2 %2← %50
∂∂(156)%3l3%2 %3n%2 %2← %3add1%2 %3n
∂∂(194)%4if%2 %3equal%2[%53%2, %3xcount%2 %3n%2]%2 %4then%2 %3return%2 %512%2 %2- %3level
∂∂(194)%4if%2 %3n%2 %2< %510%2 %4then%2 %3go%2 %3l3%2 %4else%2 %3return%2 %50%2]
∂∂(80)%4else%2 %4prog%2 %2[%3n%2]
∂∂(211)%3n%2 %2← %50
∂∂(176)%3l4%2 %3n%2 %2← %3add1%2 %3n
∂∂(211)%4if%2 %3equal%2[%53%2, %3ocount%2 %3n%2]%2 %4then%2 %3return%2 %5-12%2 %2+ %3level
∂∂(211)%4if%2 %3n%2 %2< %510%2 %4then%2 %3go%2 %3l4%2 %4else%2 %3return%2 %50



∂∂(48)%3successors%2 %3p%2 %2← %3sort%2 %3mapcar%2[%2[λ%3x%2. %3x%2 %2. %3p%2]%2, %3bs%2]



∂∂(48)%3revert%2[]%2 %2← 
∂∂(80)%4prog%2 %2[%3a%2]
∂∂(153)%3level%2 %2← %3sub1%2 %3level
∂∂(153)%3bs%2 %2← %4a %2[%4if%2 %3w%2 %4then%2 %3xs%2 %4else%2 %3os%2]%2 %2. %3bs
∂∂(153)%4if%2 %3w%2 %4then%2 %3xs%2 %2← %4d %3xs%2 %4else%2 %3os%2 %2← %4d %3os
∂∂(153)%3a%2 %2← %3lines%2 %4a %3p1
∂∂(116)%3l5%2 %4if%2 %4n %3a%2 %4then%2 %3go%2 %3l6
∂∂(153)%4if%2 %3w%2 %4then%2 %3store%2[%3xcount%2 %4a %3a%2, %3sub1%2 %3xcount%2 %4a %3a%2]%2 %4else%2 %3store%2[%3ocount%2 %4a %3a%2, %3sub1%2 %3ocount%2 %4a %3a%2]
∂∂(153)%3a%2 %2← %4d %3a
∂∂(153)%3go%2 %3l5
∂∂(116)%3l6%2 %3w%2 %2← %2¬%3w
∂∂(153)%3p1%2 %2← %4d %3p1
∂∂(153)%3return%2[]



∂∂(48)%3update%2 %3m%2 %2← 
∂∂(80)%4prog%2 %2[%3a%2]
∂∂(153)%3level%2 %2← %3add1%2 %3level
∂∂(153)%4if%2 %3w%2 %4then%2 %3os%2 %2← %3m%2 %2. %3os%2 %4else%2 %3xs%2 %2← %3m%2 %2. %3xs
∂∂(153)%3bs%2 %2← %3delete%2[%3m%2, %3bs%2]
∂∂(153)%3p1%2 %2← %3m%2 %2. %3p1
∂∂(153)%3count%2 %2← %3add1%2 %3count
∂∂(153)%3a%2 %2← %3lines%2 %3m
∂∂(119)%3l7%2 %4if%2 %4n %3a%2 %4then%2 %3go%2 %3l8
∂∂(153)%4if%2 %3w%2 %4then%2 %3store%2[%3ocount%2 %4a %3a%2, %3add1%2 %3ocount%2 %4a %3a%2]%2 %4else%2 %3store%2[%3xcount%2 %4a %3a%2, %3add1%2 %3xcount%2 %4a %3a%2]
∂∂(153)%3a%2 %2← %4d %3a
∂∂(153)%3go%2 %3l7
∂∂(116)%3l8%2 %3w%2 %2← %2¬%3w
∂∂(153)%3return%2[]



∂∂(48)%3sort%2 %3u%2 %2← %3sorta%2[%3u%2, %5NIL%2, %5NIL%2]



∂∂(48)%3sorta%2[%3u%2, %3th%2, %3ord%2]%2 %2← 
∂∂(80)%4if%2 %4n %3u%2 %4then%2 %2[%3th%2 %2* %3ord%2]
∂∂(80)%4else if%2 %3win%2 %4a %3u%2 %4then%2 %2<%4a %3u%2>
∂∂(80)%4else if%2 %3answer%2 %4a %3u%2 %4then%2 %3sortb%2[%4d %3u%2, %4a %3u%2]
∂∂(80)%4else if%2 %3doubleth%2 %4a %3u%2 %4then%2 %3sortc%2[%4d %3u%2, %4a %3u%2]
∂∂(80)%4else if%2 %3threat%2 %4a %3u%2 %4then%2 %3sorta%2[%4d %3u%2, %4a %3u%2 %2. %3th%2, %3ord%2]
∂∂(80)%4else%2 %3sorta%2[%4d %3u%2, %3th%2, %4a %3u%2 %2. %3ord%2]



∂∂(48)%3sortb%2[%3u%2, %3m%2]%2 %2← %4if%2 %4n %3u%2 %4then%2 %2<%3m%2>%2 %4else if%2 %3win%2 %4a %3u%2 %4then%2 %2<%4a %3u%2>%2 %4else%2 %3sortb%2[%4d %3u%2, %3m%2]



∂∂(48)%3sortc%2[%3u%2, %3m%2]%2 %2← 
∂∂(80)%4if%2 %4n %3u%2 %4then%2 %2<%3m%2>
∂∂(80)%4else if%2 %3win%2 %4a %3u%2 %4then%2 %2<%4a %3u%2>
∂∂(80)%4else if%2 %3answer%2 %4a %3u%2 %4then%2 %3sortb%2[%4d %3u%2, %4a %3u%2]
∂∂(80)%4else%2 %3sortc%2[%4d %3u%2, %3m%2]



∂∂(48)%3win%2 %3p%2 %2← %4if%2 %3w%2 %4then%2 %3orlis%2[%2[λ%3x%2. %3equal%2[%52%2, %3ocount%2 %3x%2]%2]%2, %3lines%2 %4a %3p%2]
∂∂(163)%4else%2 %3orlis%2[%2[λ%3x%2. %3equal%2[%52%2, %3xcount%2 %3x%2]%2]%2, %3lines%2 %4a %3p%2]



∂∂(48)%3answer%2 %3p%2 %2← 
∂∂(80)%4if%2 %3w%2 %4then%2 %3orlis%2[%2[λ%3x%2. %3equal%2[%52%2, %3xcount%2 %3x%2]%2]%2, %3lines%2 %4a %3p%2]%2 %4else%2 %3orlis%2[%2[λ%3x%2. %3equal%2[%52%2, %3ocount%2 %3x%2]%2]%2, %3lines%2 %4a %3p%2]



∂∂(48)%3doubleth%2 %3p%2 %2← 
∂∂(80)%3twolis%2[%2[λ%3x%2. 
∂∂(177)%3equal%2[%51%2, %4if%2 %3w%2 %4then%2 %3ocount%2 %3x%2 %4else%2 %3xcount%2 %3x%2]%2 %2∧ %3orlis%2[%2[λ%3w%2. %3x%2 %2ε %3lines%2 %3w%2]%2, %3delete%2[%4a %3p%2, %3bs%2]%2]%2]%2, 
∂∂(161)%3lines%2 %4a %3p%2]



∂∂(48)%3twolis%2[%3pred%2, %3u%2]%2 %2← %2¬%4n %3u%2 %2∧ %2[%2[%3pred%2 %4a %3u%2 %2∧ %3orlis%2[%3pred%2, %4d %3u%2]%2]%2 %2∨ %3twolis%2[%3pred%2, %4d %3u%2]%2]



∂∂(48)%3threat%2 %3p%2 %2← 
∂∂(80)%3orlis%2[%2[λ%3x%2. %3equal%2[%51%2, %4if%2 %3w%2 %4then%2 %3ocount%2 %3x%2 %4else%2 %3xcount%2 %3x%2]%2 %2∧ %3orlis%2[%2[λ%3w%2. %3x%2 %2ε %3lines%2 %3w%2]%2, %3delete%2[%4a %3p%2, %3bs%2]%2]%2]%2, 
∂∂(143)%3lines%2 %4a %3p%2]

.VERBATIM
.SKIP TO LINE 1
.SELECT 6
Functions on file XBASIC:

(DEFPROP BASICFNS
 (BASICFNS ORLIS ANDLIS MAPCAR2 MAPCHOOSE MAPAPP PRUP LISTSUBT LISTSUBTA CONTAINED DELETE PICKOUT PICKOUTA)
VALUE)

(DEFPROP ORLIS
 (LAMBDA (PRED U) (AND (NOT (NULL U)) (OR (PRED (CAR U)) (ORLIS PRED (CDR U)))))
EXPR)

(DEFPROP ANDLIS
 (LAMBDA (PRED U) (OR (NULL U) (AND (PRED (CAR U)) (ANDLIS PRED (CDR U)))))
EXPR)

(DEFPROP MAPCAR2
 (LAMBDA (FN U V) (COND ((NULL U) NIL) (T (CONS (FN (CAR U) (CAR V)) (MAPCAR2 FN (CDR U) (CDR V))))))
EXPR)

(DEFPROP MAPCHOOSE
 (LAMBDA(PRED FN U)
  (COND	((NULL U) NIL)
	((PRED (CAR U)) (CONS (FN (CAR U)) (MAPCHOOSE PRED FN (CDR U))))
	(T (MAPCHOOSE PRED FN (CDR U)))))
EXPR)

(DEFPROP MAPAPP
 (LAMBDA (FN U) (COND ((NULL U) NIL) (T (APPEND (FN (CAR U)) (MAPAPP FN (CDR U))))))
EXPR)

(DEFPROP PRUP
 (LAMBDA(U V)
  (COND	((NULL U) (COND ((NULL V) NIL) (T (ERROR (QUOTE (V LONGER - PRUP))))))
	((NULL V) (ERROR (QUOTE (U LONGER - PRUP))))
	(T (CONS (CONS (CAR U) (CAR V)) (PRUP (CDR U) (CDR V))))))
EXPR)

(DEFPROP LISTSUBT
 (LAMBDA (U V) (LISTSUBTA U (DIFFERENCE (LENGTH U) (LENGTH V)) NIL))
EXPR)

(DEFPROP LISTSUBTA
 (LAMBDA (U N Z) (COND ((EQUAL N 0) Z) (T (LISTSUBTA (CDR U) (SUB1 N) (CONS (CAR U) Z)))))
EXPR)

(DEFPROP CONTAINED
 (LAMBDA (U V) (OR (NULL U) (AND (MEMBER (CAR U) V) (CONTAINED (CDR U) V))))
EXPR)

(DEFPROP DELETE
 (LAMBDA (X U) (COND ((NULL U) NIL) ((EQUAL X (CAR U)) (CDR U)) (T (CONS (CAR U) (DELETE X (CDR U))))))
EXPR)

(DEFPROP PICKOUT
 (LAMBDA (PRED U) (PICKOUTA PRED U NIL NIL))
EXPR)

(DEFPROP PICKOUTA
 (LAMBDA(PRED U X Y)
  (COND	((NULL U) (CONS X Y))
	((PRED (CAR U)) (PICKOUTA PRED (CDR U) (CONS (CAR U) X) Y))
	(T (PICKOUTA PRED (CDR U) X (CONS (CAR U) Y)))))
EXPR)



Functions on file XGAME:

(DEFPROP GAMEFNS
 (GAMEFNS VALMAX VALMIN LINEMAX LINEMIN TREEMAX TREEMIN RECTIFY COMMONTAIL COMMONHEAD)
VALUE)

(DEFPROP VALMAX
 (LAMBDA(U ALPHA BETA)
  (COND	((NULL U) ALPHA)
	(T
	 ((LAMBDA(S)
	   (COND ((NOT (GREATERP S ALPHA)) (VALMAX (CDR U) ALPHA BETA))
		 ((LESSP S BETA) (VALMAX (CDR U) S BETA))
		 (T BETA)))
	  (COND	((TER (RECTIFY (CAR U)) ALPHA BETA) (IMVAL (CAR U)))
		(T (VALMIN (SUCCESSORS (CAR U)) ALPHA BETA)))))))
EXPR)

(DEFPROP VALMIN
 (LAMBDA(U ALPHA BETA)
  (COND	((NULL U) BETA)
	(T
	 ((LAMBDA(S)
	   (COND ((NOT (GREATERP S ALPHA)) ALPHA)
		 ((LESSP S BETA) (VALMIN (CDR U) ALPHA S))
		 (T (VALMIN (CDR U) ALPHA BETA))))
	  (COND	((TER (RECTIFY (CAR U)) ALPHA BETA) (IMVAL (CAR U)))
		(T (VALMAX (SUCCESSORS (CAR U)) ALPHA BETA)))))))
EXPR)

(DEFPROP LINEMAX
 (LAMBDA(U LINE ALPHA BETA)
  (COND	((NULL U) (CONS ALPHA LINE))
	(T
	 ((LAMBDA(S)
	   (COND ((NOT (GREATERP (CAR S) ALPHA)) (LINEMAX (CDR U) LINE ALPHA BETA))
		 ((LESSP (CAR S) BETA) (LINEMAX (CDR U) (CONS (EXT (CAR U)) (CDR S)) (CAR S) BETA))
		 (T (CONS BETA LINE))))
	  (COND	((TER (RECTIFY (CAR U)) ALPHA BETA) (LIST (IMVAL (CAR U))))
		(T (LINEMIN (SUCCESSORS (CAR U)) (CONS BETA (QUOTE BETA-CUTOFF)) ALPHA BETA)))))))
EXPR)

(DEFPROP LINEMIN
 (LAMBDA(U LINE ALPHA BETA)
  (COND	((NULL U) (CONS BETA LINE))
	(T
	 ((LAMBDA(S)
	   (COND ((NOT (GREATERP (CAR S) ALPHA)) (CONS ALPHA LINE))
		 ((LESSP (CAR S) BETA) (LINEMIN (CDR U) (CONS (EXT (CAR U)) (CDR S)) ALPHA (CAR S)))
		 (T (LINEMIN (CDR U) LINE ALPHA BETA))))
	  (COND	((TER (RECTIFY (CAR U)) ALPHA BETA) (LIST (IMVAL (CAR U))))
		(T (LINEMAX (SUCCESSORS (CAR U)) (CONS ALPHA (QUOTE ALPHA-CUTOFF)) ALPHA BETA)))))))
EXPR)

(DEFPROP TREEMAX
 (LAMBDA(U TRMAX TRMIN ALPHA BETA)
  (COND	((NULL U) (LIST ALPHA TRMAX TRMIN))
	(T
	 ((LAMBDA(S)
	   (COND ((NOT (GREATERP (CAR S) ALPHA))
		  (TREEMAX (CDR U) TRMAX (CONS (CONS (EXT (CAR U)) (CADDR S)) TRMIN) ALPHA BETA))
		 ((LESSP (CAR S) BETA)
		  (TREEMAX (CDR U)
			   (CONS (EXT (CAR U)) (CADR S))
			   (CONS (CONS (EXT (CAR U)) (CADDR S)) TRMIN)
			   (CAR S)
			   BETA))
		 (T (LIST BETA (CONS (EXT (CAR U)) (CADR S)) NIL))))
	  (COND	((TER (RECTIFY (CAR U)) ALPHA BETA) ((LAMBDA (V) (LIST V (LIST V) (LIST V))) (IMVAL (CAR U))))
		(T (TREEMIN (SUCCESSORS (CAR U)) NIL (CONS BETA (QUOTE BETA-CUTOFF)) ALPHA BETA)))))))
EXPR)

(DEFPROP TREEMIN
 (LAMBDA(U TRMAX TRMIN ALPHA BETA)
  (COND	((NULL U) (LIST BETA TRMAX TRMIN))
	(T
	 ((LAMBDA(S)
	   (COND ((NOT (GREATERP (CAR S) ALPHA)) (LIST ALPHA NIL (CONS (EXT (CAR U)) (CADDR S))))
		 ((LESSP (CAR S) BETA)
		  (TREEMIN (CDR U)
			   (CONS (CONS (EXT (CAR U)) (CADR S)) TRMAX)
			   (CONS (EXT (CAR U)) (CADDR S))
			   ALPHA
			   (CAR S)))
		 (T (TREEMIN (CDR U) (CONS (CONS (EXT (CAR U)) (CADR S)) TRMAX) TRMIN ALPHA BETA))))
	  (COND	((TER (RECTIFY (CAR U)) ALPHA BETA) ((LAMBDA (V) (LIST V (LIST V) (LIST V))) (IMVAL (CAR U))))
		(T (TREEMAX (SUCCESSORS (CAR U)) (CONS ALPHA (QUOTE ALPHA-CUTOFF)) NIL ALPHA BETA)))))))
EXPR)

(DEFPROP RECTIFY
 (LAMBDA(P)
  (PROG	(Z Q)
	(SETQ Q (COMMONTAIL P P1))
   L1	(COND ((EQUAL Q P1) (GO L2)))
	(REVERT)
	(GO L1)
   L2	(SETQ Z (LISTSUBT P P1))
   L3	(COND ((NULL Z) (RETURN P)))
	(UPDATE (CAR Z))
	(SETQ Z (CDR Z))
	(GO L3)))
EXPR)

(DEFPROP COMMONTAIL
 (LAMBDA (U V) (REVERSE (COMMONHEAD (REVERSE U) (REVERSE V))))
EXPR)

(DEFPROP COMMONHEAD
 (LAMBDA(U V)
  (COND	((OR (NULL U) (NULL V) (NOT (EQUAL (CAR U) (CAR V)))) NIL)
	(T (CONS (CAR U) (COMMONHEAD (CDR U) (CDR V))))))
EXPR)


Functions on file TICTAC:

(DEFPROP TICTACFNS
 (TRY2 COMMENCE
       EXT
       NEWGAME
       TER
       IMVAL
       SUCCESSORS
       REVERT
       UPDATE
       PTS
       LINES
       SORT
       SORTA
       SORTB
       SORTC
       WIN
       ANSWER
       DOUBLETH
       TWOLIS
       THREAT)
VALUE)

(DEFPROP COMMENCE
 (LAMBDA NIL
  (PROG	NIL
	(ARRAY LINES T 12)
	(ARRAY XCOUNT 44 11)
	(ARRAY OCOUNT 44 11)
	(STORE (LINES 1) (QUOTE (1 4 7)))
	(STORE (LINES 2) (QUOTE (1 5)))
	(STORE (LINES 3) (QUOTE (1 6 10)))
	(STORE (LINES 4) (QUOTE (2 4)))
	(STORE (LINES 5) (QUOTE (2 5 7 10)))
	(STORE (LINES 6) (QUOTE (2 6)))
	(STORE (LINES 7) (QUOTE (3 4 10)))
	(STORE (LINES 10) (QUOTE (3 5)))
	(STORE (LINES 11) (QUOTE (3 6 7)))))
EXPR)

(DEFPROP EXT
 (LAMBDA (P) (CAR P))
EXPR)

(DEFPROP NEWGAME
 (LAMBDA NIL
  (PROG	(N)
	(SETQ N 0)
   L	(SETQ N (ADD1 N))
	(STORE (XCOUNT N) 0)
	(STORE (OCOUNT N) 0)
	(COND ((LESSP N 10) (GO L)))
	(SETQ P1 NIL)
	(SETQ XS NIL)
	(SETQ OS NIL)
	(SETQ BS (QUOTE (1 2 3 4 5 6 7 10 11)))
	(SETQ W NIL)
	(SETQ LEVEL 0)
	(SETQ COUNT 0)
	(RETURN (QUOTE (NEW GAME)))))
EXPR)

(DEFPROP TER
 (LAMBDA(P ALPHA BETA)
  (AND (NOT (NULL P))
       (OR (EQUAL LEVEL 11)
	   (LESSP (DIFFERENCE 11 LEVEL) ALPHA)
	   (GREATERP (PLUS -11 LEVEL) BETA)
	   (PROG (N)
		 (SETQ N 0)
	    L2	 (SETQ N (ADD1 N))
		 (COND ((EQUAL 3 (COND (W (XCOUNT N)) (T (OCOUNT N)))) (RETURN T)))
		 (COND ((LESSP N 10) (GO L2)))
		 (RETURN NIL)))))
EXPR)

(DEFPROP IMVAL
 (LAMBDA(P)
  (COND	(W
	 (PROG (N)
	       (SETQ N 0)
	  L3   (SETQ N (ADD1 N))
	       (COND ((EQUAL 3 (XCOUNT N)) (RETURN (DIFFERENCE 12 LEVEL))))
	       (COND ((LESSP N 10) (GO L3)) (T (RETURN 0)))))
	(T
	 (PROG (N)
	       (SETQ N 0)
	  L4   (SETQ N (ADD1 N))
	       (COND ((EQUAL 3 (OCOUNT N)) (RETURN (PLUS -12 LEVEL))))
	       (COND ((LESSP N 10) (GO L4)) (T (RETURN 0)))))))
EXPR)

(DEFPROP SUCCESSORS
 (LAMBDA (P) (SORT (MAPCAR (FUNCTION (LAMBDA (X) (CONS X P))) BS)))
EXPR)

(DEFPROP REVERT
 (LAMBDA NIL
  (PROG	(A)
	(SETQ LEVEL (SUB1 LEVEL))
	(SETQ BS (CONS (CAR (COND (W XS) (T OS))) BS))
	(COND (W (SETQ XS (CDR XS))) (T (SETQ OS (CDR OS))))
	(SETQ A (LINES (CAR P1)))
   L5	(COND ((NULL A) (GO L6)))
	(COND (W (STORE (XCOUNT (CAR A)) (SUB1 (XCOUNT (CAR A)))))
	      (T (STORE (OCOUNT (CAR A)) (SUB1 (OCOUNT (CAR A))))))
	(SETQ A (CDR A))
	(GO L5)
   L6	(SETQ W (NOT W))
	(SETQ P1 (CDR P1))
	(RETURN)))
EXPR)

(DEFPROP UPDATE
 (LAMBDA(M)
  (PROG	(A)
	(SETQ LEVEL (ADD1 LEVEL))
	(COND (W (SETQ OS (CONS M OS))) (T (SETQ XS (CONS M XS))))
	(SETQ BS (DELETE M BS))
	(SETQ P1 (CONS M P1))
	(SETQ COUNT (ADD1 COUNT))
	(SETQ A (LINES M))
   L7	(COND ((NULL A) (GO L8)))
	(COND (W (STORE (OCOUNT (CAR A)) (ADD1 (OCOUNT (CAR A)))))
	      (T (STORE (XCOUNT (CAR A)) (ADD1 (XCOUNT (CAR A))))))
	(SETQ A (CDR A))
	(GO L7)
   L8	(SETQ W (NOT W))
	(RETURN)))
EXPR)

(DEFPROP SORT
 (LAMBDA (U) (SORTA U NIL NIL))
EXPR)

(DEFPROP SORTA
 (LAMBDA(U TH ORD)
  (COND	((NULL U) (APPEND TH ORD))
	((WIN (CAR U)) (LIST (CAR U)))
	((ANSWER (CAR U)) (SORTB (CDR U) (CAR U)))
	((DOUBLETH (CAR U)) (SORTC (CDR U) (CAR U)))
	((THREAT (CAR U)) (SORTA (CDR U) (CONS (CAR U) TH) ORD))
	(T (SORTA (CDR U) TH (CONS (CAR U) ORD)))))
EXPR)

(DEFPROP SORTB
 (LAMBDA (U M) (COND ((NULL U) (LIST M)) ((WIN (CAR U)) (LIST (CAR U))) (T (SORTB (CDR U) M))))
EXPR)

(DEFPROP SORTC
 (LAMBDA(U M)
  (COND	((NULL U) (LIST M))
	((WIN (CAR U)) (LIST (CAR U)))
	((ANSWER (CAR U)) (SORTB (CDR U) (CAR U)))
	(T (SORTC (CDR U) M))))
EXPR)

(DEFPROP WIN
 (LAMBDA(P)
  (COND	(W (ORLIS (FUNCTION (LAMBDA (X) (EQUAL 2 (OCOUNT X)))) (LINES (CAR P))))
	(T (ORLIS (FUNCTION (LAMBDA (X) (EQUAL 2 (XCOUNT X)))) (LINES (CAR P))))))
EXPR)

(DEFPROP ANSWER
 (LAMBDA(P)
  (COND	(W (ORLIS (FUNCTION (LAMBDA (X) (EQUAL 2 (XCOUNT X)))) (LINES (CAR P))))
	(T (ORLIS (FUNCTION (LAMBDA (X) (EQUAL 2 (OCOUNT X)))) (LINES (CAR P))))))
EXPR)

(DEFPROP DOUBLETH
 (LAMBDA(P)
  (TWOLIS (FUNCTION
	   (LAMBDA(X)
	    (AND (EQUAL 1 (COND (W (OCOUNT X)) (T (XCOUNT X))))
		 (ORLIS (FUNCTION (LAMBDA (W) (MEMBER X (LINES W)))) (DELETE (CAR P) BS)))))
	  (LINES (CAR P))))
EXPR)

(DEFPROP TWOLIS
 (LAMBDA (PRED U) (AND (NOT (NULL U)) (OR (AND (PRED (CAR U)) (ORLIS PRED (CDR U))) (TWOLIS PRED (CDR U)))))
EXPR)

(DEFPROP THREAT
 (LAMBDA(P)
  (ORLIS (FUNCTION
	  (LAMBDA(X)
	   (AND	(EQUAL 1 (COND (W (OCOUNT X)) (T (XCOUNT X))))
		(ORLIS (FUNCTION (LAMBDA (W) (MEMBER X (LINES W)))) (DELETE (CAR P) BS)))))
	 (LINES (CAR P))))
EXPR)
.SKIP TO LINE 1
.SELECT 5
Examples:
(At the beginning, you must call the functions COMMENCE and NEWGAME.)


*(VALMIN @((2 1)) -100 100)

3 


*(LINEMIN @((2 1)) NIL -100 100)

(3 2 7 4 5 11 3) 


*(SPRINT (TREEMIN @((2 1)) NIL NIL -100 100) 1)

(3 ((2 4 (7 5 (6 11 3))))
   (2 (6 5 (10 3 (7 0)))
      (10 6 (11 5 (7 3)))
      (3 10 (5 11 (7 3)))
      (5 11 (7 4 (3 3)))
      (7 4 (11 5 (10 3)))
      (11 5 (10 7 (3 0)))
      (4 7 (5 6 (11 3)))))


*(VALMIN @((5 1)) -100 100)

0 


*(LINEMIN @((5 1)) NIL -100 100)

(0 5 4 7 3 2 10 11 6) 


*(SPRINT (TREEMIN @((5 1)) NIL NIL -100 100) 1)

(0 ((5 4 (7 3 (2 10 (6 11 0) (11 6 0)))))
   (5 (6 2 (10 7 (3 11 (4 0))))
      (10 6 (4 7 (3 2 (11 0))))
      (11 10 (2 3 (7 4 (6 0))))
      (2 3 (7 4 (6 11 (10 0))))
      (7 4 (6 10 (2 3 (11 0))))
      (3 2 (10 6 (4 7 (11 0))))
      (4 7 (3 2 (10 11 (6 0))))))
.END